package lbj.cyw.dp;

/*279. 完全平方数
        完全背包问题

        f(i)=min{f(i-j*j)}+1;
            j*j<=i;
* */
public class NumSquares279 {
    public int numSquares(int n) {
        if(n==1){
            return 1;
        }
        int[] dp=new int[n+1];
        dp[0]=0;
        for(int i=1;i<=n;i++){
            dp[i]=Integer.MAX_VALUE;
            for(int j=1; j*j<=i;j++){
                dp[i]=Math.min(dp[i-j*j]+1,dp[i]);
            }
        }
        return dp[n];
    }
}
